package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no42;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        //[0,1,0,2,1,0,1,3,2,1,2,1]
        //6
        System.out.println(solution.trap2(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    public int trap(int[] height) {
        int sum = 0;
        int len = height.length;
        if (len <= 2) {
            return sum;
        }
        int[] maxL = new int[len];
        int maxLeft = height[0];
        for (int i = 0; i < len; i++) {
            maxLeft = Math.max(maxLeft, height[i]);
            maxL[i] = maxLeft;
        }
        int[] maxR = new int[len];
        int maxRight = height[len - 1];
        for (int i = len - 1; i >= 0; i--) {
            maxRight = Math.max(maxRight, height[i]);
            maxR[i] = maxRight;
        }
        for (int i = 0; i < len; i++) {
            sum += Math.min(maxL[i], maxR[i]) - height[i];
        }
        return sum;
    }

    public int trap2(int[] height) {
        int l = 0, r = height.length - 1;
        int sum = 0;
        int lMax = Integer.MIN_VALUE, rMax = Integer.MIN_VALUE;
        while(l < r){
            lMax = Math.max(lMax, height[l]);
            rMax = Math.max(rMax, height[r]);
            if(lMax > rMax){
                sum += rMax - height[r];
                r --;
            }
            else{
                sum += lMax - height[l];
                l ++;
            }
        }
        return sum;
    }
}
